class Solution
{
public:
    bool validUtf8(vector<int> &data)
    {
        int i = 0;
        int n = data.size();

        auto checkNextBytes = [&](int index, int nBytes)
        {
            if (index + nBytes >= n)
            {
                return false;
            }
            for (int i = 1; i <= nBytes; ++i)
            {
                if (data[index + i] >> 6 != 0b10)
                {
                    return false;
                }
            }
            return true;
        };

        while (i < n)
        {
            int head = data[i];
            if (!(head & (1 << 7)))
            {
                ++i;
            }
            else
            {
                int nBytes = -1;
                if (head >> 5 == 0b110)
                {
                    nBytes = 1;
                }
                else if (head >> 4 == 0b1110)
                {
                    nBytes = 2;
                }
                else if (head >> 3 == 0b11110)
                {
                    nBytes = 3;
                }
                if (nBytes == -1)
                {
                    return false;
                }
                if (checkNextBytes(i, nBytes) == false)
                {
                    return false;
                }
                i += nBytes + 1;
            }
        }
        return true;
    }
};